Medical facilities have come to rely more and more on computerized systems for the purposes of diagnosis and therapy.
Many medical imaging processes are based on high quality volumetric image data acquired by computer-controlled high performance modalities such as computer tomographs (CT), positron emission tomographs (PET) and magnetic resonance (MR) scanners. In general, three-dimensional (3D) volumetric image data are processed by modern volume rendering processors to obtain two-dimensional (2D) cross-sectional views, called slices, which are then visually examined by the radiologist for the purposes of diagnosis or therapy. The slices allow the radiologist to examine a condition of a patient as they show a cross-sectional representation of an organ of interest, for example the liver or the kidneys of a patient, afflicted for example by a tumor. The information in the slices relevant for diagnosis or therapy, that is information related to the organ of interest, is referred to as regions of interest.
The regions of interest are defined by coordinates of pixels in the slice or a number of parallel, spatially adjacent slices of a volumetric image data set. The regions of interest must first be extracted by a procedure known as segmentation before they can be made accessible to a post-processing computer system for the purposes of diagnosis, therapy or follow-up. The segmentation of the slices allows the radiologist to obtain a coordinate-wise definition of the regions of interest and to feed this information for example into a control unit of a linear accelerator for the purposes of radiotherapy. The linear accelerator can then be controlled such as to direct a beam to a specific organ of the patient as defined by the regions of interest, for example a cancerous liver.
Currently, the segmentation of the regions of interest is performed manually or semi-automatically by the radiologist. The radiologist uses for example a mouse or other pointer tools to outline the regions within the slices by contours. The coordinates within the slices marked by the contours are then translated into polygons by mathematical or CAD software systems and fed into dedicated segmentation supporting software systems.
There are known in the state of the prior art a number of such segmentation supporting software systems, for example “Live Wire”, “Live Lane” or “Interactive Active Contours”. The volumetric image data captured by the high performance medical modalities are capable of acquiring the slices in smaller than 0.5 mm intervals across an axis of the patient. This results in the organ of interest to be represented by the regions of interest being distributed across many hundreds of adjacent slices. Marking the regions of interest within each one of those slices is therefore not feasible. The segmentation supporting software system assists the radiologist in this tedious and time consuming but all the more important task of segmentation of regions of interest by using a number of different interpolation algorithms.
These algorithms interpolate from an ideally small number of polygons representing the contours of the regions of interest in those slices actually marked by the radiologist to obtain intermediate polygons and ultimately contours for the regions of interest within the slices not marked by the radiologist.
The polygon interpolation algorithms also known as “contour morphing”, “two-dimensional shape blending”, or “boundary mapping”, take as input two adjacent polygons from which the intermediate polygon is interpolated.
The polygon interpolation algorithms normally comprise a step of calculating pairs of corresponding points from among the points of the two polygons.
Each point in the pair of corresponding points is from different ones of the two polygons. The pairs of corresponding points are then used for the actual interpolation of the points of the intermediate polygon, each pair yielding an point of the intermediate polygon.
Furthermore, the interpolation algorithms are based on a similarity measure used as normally restricting or constraining the step of determining the pairs of corresponding points. However, interpolation algorithms used in current segmentation supporting software systems are suffering from a number of shortcomings.
The segmentation supporting software systems relying for example on the boundary based parametric polygon morphing algorithm by D. H. Chen and Y. N. Sun (IEICE Transactions and Information Systems, Vol. E84-D, No. 4, pp. 511-520, 2001) necessitate a high degree of interactivity as they require the radiologist to prescribe corresponding points manually between the polygons. Although this system somewhat cuts down the time for performing the segmentation in that the radiologist is no longer needed to perform the segmentations on all of the slices, it still remains a time consuming task due to the semi-automatic character of this algorithm.
Furthermore, the method by Chen & Sun requires the slices from which the two polygons have been derived to be parallel. The applicability of this algorithm for clinical purposes is therefore restricted.
Other polygon algorithms lead to prohibitively long computation times, thus rendering corresponding segmentation supporting software systems unsuitable for the fast-paced clinical environment.
Those polygon interpolation algorithms scale quadratically or even cubically with a number of sampling points on the two polygons used for the interpolation. The reason for those time complexities is manifold. For example, some of the polygon interpolation algorithms require a comparison of each point of one of the polygons with each of the points of the other polygon. Examples of algorithms having higher complexity are provided by algorithm basing the step of determining corresponding points on the rasterization of areas enclosed by each of the two polygons, see for example G. M. Treece et al., “Surface interpolation from sparse cross sections using region correspondence,” IEEE Transactions on Medical Imaging (Vol. 19, No. 11, pp 1106-1114, November 2000) or first deriving a skeleton of the polygonal shape, see for example G. Barequet et al., “Contour interpolation by straight skeletons,” Graphical Models (Vol. 66, No. 4, pp 245-260, July 2004). Other examples are the polygon interpolation algorithm according to A. Efrat et al. that uses a similarity measure based on “geodesic width” or “link-width” which ultimately results in the algorithm to scale quadratically with the number of sample points.
As segmentation lies at the heart of many important diagnostic and therapeutic processes there is a need for fast and efficient polygon interpolation algorithms. There is also a need for a polygon interpolation algorithm that is fully automatic and only requires a minimal degree of user interaction.
There is a further need for a polygon interpolation algorithm that can dispense with the requirement of polygons being derived from parallel slices.
There is furthermore a need in the art for a polygon interpolation algorithm that scales less than quadratically with the number of sampling points.